|
In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the size of the largest clique of that subgraph. Due to the strong perfect graph theorem, perfect graphs are the same as Berge graphs. A graph G is a Berge graph if neither G nor its complement has an odd-length induced cycle of length 5 or more. The perfect graphs include many important families of graphs, and serve to unify results relating colorings and cliques in those families. For instance, in all perfect graphs, the graph coloring problem, maximum clique problem, and maximum independent set problem can all be solved in polynomial time. In addition, several important min-max theorems in combinatorics, such as Dilworth's theorem, can be expressed in terms of the perfection of certain associated graphs. The theory of perfect graphs developed from a 1958 result of Tibor Gallai that in modern language can be interpreted as stating that the complement of a bipartite graph is perfect; this result can also be viewed as a simple equivalent of König's theorem, a much earlier result relating matchings and vertex covers in bipartite graphs. The first use of the phrase "perfect graph" appears to be in a 1963 paper of Claude Berge, after whom Berge graphs are named. In this paper he unified Gallai's result with several similar results by defining perfect graphs, and he conjectured the equivalence of the perfect graph and Berge graph definitions; Berge's conjecture was proved in 2002 as the strong perfect graph theorem. ==Families of graphs that are perfect== Some of the more well-known perfect graphs are: * Bipartite graphs, the graphs that can be colored with two colors, including the forests, graphs with no cycles. * The line graphs of bipartite graphs (see König's theorem). The rook's graphs (line graphs of complete bipartite graphs) are a special case. * Chordal graphs, the graphs in which every cycle of four or more vertices has a ''chord'', an edge between two vertices that are not consecutive in the cycle. These include the forests, ''k''-trees (maximal graphs with a given treewidth), split graphs (graphs that can be partitioned into a clique and an independent set), block graphs (graphs in which every biconnected component is a clique), interval graphs (graphs in which each vertex represents an interval of a line and each edge represents a nonempty intersection between two intervals), trivially perfect graphs (interval graphs for nested intervals), threshold graphs (graphs in which two vertices are adjacent when their total weight exceeds a numerical threshold), windmill graphs (formed by joining equal cliques at a common vertex), and strongly chordal graphs (chordal graphs in which every even cycle of length six or more has an odd chord). * Comparability graphs formed from partially ordered sets by connecting pairs of elements by an edge whenever they are related in the partial order. These include the bipartite graphs, the complements of interval graphs, the trivially perfect graphs, the threshold graphs, the windmill graphs, the permutation graphs (graphs in which the edges represent pairs of elements that are reversed by a permutation), and the cographs (graphs formed by recursive operations of disjoint union and complementation). * Perfectly orderable graphs, the graphs that can be ordered in such a way that a greedy coloring algorithm is optimal on every induced subgraph. These include the bipartite graphs, the chordal graphs, the comparability graphs, the distance-hereditary graphs (in which shortest path distances in connected induced subgraphs equal those in the whole graph), and the wheel graphs that have an odd number of vertices. * Trapezoid graphs, the intersection graphs of trapezoids whose parallel pairs of edges lie on two parallel lines. These include the interval graphs, trivially perfect graphs, threshold graphs, windmill graphs, and permutation graphs; their complements are a subset of the comparability graphs. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Perfect graph」の詳細全文を読む スポンサード リンク
|